package org.review.algorithm.stack;

import sun.java2d.Surface;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class PolishNotation {
    public static void main(String[] args) {
        //先定义给逆波兰表达式
        //(30+4)×5-6 => 30 4 + 5 × 6 - => 164

       /* String expression = "30 4 + 5 * 6 -";
        PolishNotation polishNotation = new PolishNotation();
        List<String> list = polishNotation.getList(expression);
        System.out.println(list);
        System.out.println(polishNotation.calc(list));*/
        //String expression = "1+((2+3)*4)-5";
        String expression = "1+((1+4+20*3)×4)-5";
        PolishNotation polishNotation = new PolishNotation();
        List<String> expressionList = polishNotation.toExpressionList(expression);
        System.out.println(expressionList);
        List<String> polishNotation1 = polishNotation.toPolishNotation(expressionList);
        System.out.println(polishNotation1);
        System.out.println(polishNotation.calc(polishNotation1));
    }

    public List<String> getList(String expression) {
        String[] strList = expression.split(" ");
        return Arrays.asList(strList);
    }

    public int calc(List<String> strList) {

        Stack<String> stack = new Stack<>();
        for (String str : strList) {
            boolean matches = str.matches("\\d+");
            if (matches) {
                stack.push(str);
            } else {
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                int res = 0;
                switch (str) {
                    case "+":
                        res = num1 + num2;
                        break;
                    case "-":
                        res = num2 - num1;
                        break;
                    case "*":
                    case "×":
                        res = num1 * num2;
                        break;
                    case "/":
                        res = num2 / num1;
                        break;
                }
                stack.push(String.valueOf(res));
            }
        }

        return Integer.parseInt(stack.pop());
    }

    public List<String> toExpressionList(String expression) {

        List<String> list = new ArrayList<>();

        int index = 0;
        String stempStr = "";
        while (index < expression.length()) {

            String subStr = expression.substring(index, index + 1);
            if (!subStr.matches("\\d+")) {
                list.add(subStr);
            } else {
                stempStr += subStr;
                if (index == expression.length() - 1) {
                    list.add(stempStr);
                } else if (!expression.substring(index + 1, index + 2).matches("\\d+")) {
                    list.add(stempStr);
                    stempStr = "";
                }
            }
            index++;
        }

        return list;
    }

    //TODO 逆波兰表达式转换

    /**
     * 将中缀表达式添加小括号，然后将括号内的符号放到括号外边并消除括号就是后缀表达式
     * @param expressList
     * @return
     */
    public List<String> toPolishNotation(List<String> expressList) {
        Stack<String> operaStack = new Stack<String>();
        List<String> suffixList = new ArrayList<>();
//1+((1+4+2*3)×4)-5
        for (String item : expressList) {
            if (item.matches("\\d+")) {
                suffixList.add(item);
            } else {
                if (operaStack.isEmpty() || "(".equals(item)) { //TODO 如果操作栈为空或item是（ 直接压栈
                    operaStack.push(item);
                } else if (priority(operaStack.peek()) < priority(item)) {//TODO 如果大于操作栈顶元素压入到操作符栈顶
                    operaStack.push(item);
                } else if (")".equals(item)) { //TODO 操作符弹栈遇到（ 停止 并将（）废弃
                    while (!operaStack.isEmpty() && !operaStack.peek().equals("(")) {
                        suffixList.add(operaStack.pop());
                    }
                    operaStack.pop();
                } else {//TODO item优先级小于操作符栈顶元素 将操作栈顶元素压入临时栈
                    while (!operaStack.isEmpty() && priority(operaStack.peek()) >= priority(item)) {
                        suffixList.add(operaStack.pop());
                    }
                    operaStack.push(item);
                }
            }
        }
        //TODO 将所有操做栈的操作符弹出到临时栈中
        while (!operaStack.isEmpty()) {
            suffixList.add(operaStack.pop());
        }


        return suffixList;
    }

    public int priority(String str) {
        int priority = -1;

        if ("*".equals(str) || "/".equals(str) || "×".equals(str)) { //TODO 兼容*和×
            priority = 1;
        } else if ("+".equals(str) || "-".equals(str)) {
            priority = 0;
        }
        return priority;
    }
}
